package 动态规划.斐波那契数模型;


/**
 * 解码方法:
 */
public class likou91 {

    // dp 表不多加
    public int numDecodings(String ss) {
        char[] s = ss.toCharArray();
        int n = ss.length();
        int[] dp = new int[n]; //不多开辟一个空间

        // 第一个位置
        if(s[0] != '0') dp[0] = 1; // 假如可以解码成功就是1, 不成功就是0
        if(n == 1) return dp[0];

        // 第二个位置
        if(s[0] != '0' && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + s[1] - '0';
        if(t >= 10 && t <= 26) dp[1] += 1;

        for (int i = 2; i < n; i++) {
            // 单独可以解码成功
            if(s[i] != '0') dp[i] += dp[i - 1];
            // 两个拼一块可以解码成功
            int tmp = (s[i - 1] - '0') * 10 + s[i] - '0';
            if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
        }
        return dp[n - 1]; // 注意多加了一个位置, 所以就不是 dp[n - 1]
    }

    // 多加一个 节点
    public int numDecodings1(String ss) {
        char[] s = ss.toCharArray();
        int n = ss.length();
        int[] dp = new int[n + 1]; // 多开辟一个空间

        dp[0] = 1; // 确保后面的值是正确的
        if(s[1- 1] != '0') dp[1] = 1; // 假如可以解码成功就是1, 不成功就是0

        for (int i = 2; i <= n; i++) {
            // 单独可以解码成功
            if(s[i - 1] != '0') dp[i] += dp[i - 1];
            // 两个拼一块可以解码成功
            int tmp = (s[i - 1 - 1] - '0') * 10 + s[i - 1] - '0';
            if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
        }
        return dp[n]; // 注意多加了一个位置, 所以就不是 dp[n - 1]
    }

}
